Finding effectors in social networks.

GraSS Graph Structure Summarization.

Reconstructing Randomized Social Networks.

EventSummarizer a tool for summarizing large event sequences.

A Framework for Computing the Privacy Scores of Users in Online Social Networks.
Abstract—A large body of work has been devoted to address corporate-scale privacy concerns related to social networks. The main focus was on how to share social networks owned by organizations without revealing the identities or sensitive relationships of the users involved. Not much attention has been given to the privacy risk of users posed by their informationsharing activities. In this paper, we approach the privacy concerns arising in online social networks from the individual users ’ viewpoint: we propose a framework to compute a privacy score of a user, which indicates the potential privacy risk caused by his participation in the network. Our definition of privacy score satisfies the following intuitive properties: the more sensitive the information revealed by a user, the higher his privacy risk. Also, the more visible the disclosed information becomes in the network, the higher the privacy risk. We develop mathematical models to estimate both sensitivity and visibility of the information. We apply our methods to synthetic and real-world data and demonstrate their efficacy and practical utility. Keywords-privacy score; social network; item response theory I.
A Framework for Computing the Privacy Scores of Users in Online Social Networks.
Abstract—A large body of work has been devoted to address corporate-scale privacy concerns related to social networks. The main focus was on how to share social networks owned by organizations without revealing the identities or sensitive relationships of the users involved. Not much attention has been given to the privacy risk of users posed by their informationsharing activities. In this paper, we approach the privacy concerns arising in online social networks from the individual users ’ viewpoint: we propose a framework to compute a privacy score of a user, which indicates the potential privacy risk caused by his participation in the network. Our definition of privacy score satisfies the following intuitive properties: the more sensitive the information revealed by a user, the higher his privacy risk. Also, the more visible the disclosed information becomes in the network, the higher the privacy risk. We develop mathematical models to estimate both sensitivity and visibility of the information. We apply our methods to synthetic and real-world data and demonstrate their efficacy and practical utility. Keywords-privacy score; social network; item response theory I.
Finding a team of experts in social networks.
Given a task T, a pool of individuals X with different skills, and a social network G that captures the compatibility among these individuals, we study the problem of finding X ′ , a subset of X, to perform the task. We call this the Team Formation problem. We require that members of X ′ not only meet the skill requirements of the task, but can also work effectively together as a team. We measure effectiveness using the communication cost incurred by the subgraph in G that only involves X ′. We study two variants of the problem for two different communication-cost functions, and show that both variants are NP-hard. We explore their connections with existing combinatorial problems and give novel algorithms for their solution. To the best of our knowledge, this is the first work to consider the Team Formation problem in the presence of a social network of individuals. Experiments on the DBLP dataset show that our framework works well in practice and gives useful and intuitive results.
Finding a team of experts in social networks.
Given a task T, a pool of individuals X with different skills, and a social network G that captures the compatibility among these individuals, we study the problem of finding X ′ , a subset of X, to perform the task. We call this the Team Formation problem. We require that members of X ′ not only meet the skill requirements of the task, but can also work effectively together as a team. We measure effectiveness using the communication cost incurred by the subgraph in G that only involves X ′. We study two variants of the problem for two different communication-cost functions, and show that both variants are NP-hard. We explore their connections with existing combinatorial problems and give novel algorithms for their solution. To the best of our knowledge, this is the first work to consider the Team Formation problem in the presence of a social network of individuals. Experiments on the DBLP dataset show that our framework works well in practice and gives useful and intuitive results.
Efficient Privacy%2DPreserving Link Discovery.
Abstract. Link discovery is a process of identifying association(s) among different entities included in a complex network structure. These association(s) may represent any interaction among entities, for example between people or even bank accounts. The need for link discovery arises in many applications including law enforcement, counter-terrorism, social network analysis, intrusion detection, and fraud detection. Given the sensitive nature of information that can be revealed from link discovery, privacy is a major concern from the perspective of both individuals and organizations. For example, in the context of financial fraud detection, linking transactions may reveal sensitive information about other individuals not involved in any fraud. It is known that link discovery can be done in a privacy-preserving manner by securely finding the transitive closure of a graph. We propose two very efficient techniques to find the transitive closure securely. The two protocols have varying levels of security and performance. We analyze the performance and usability of the proposed approach in terms of both analytical and experimental results.
Finding Links and Initiators A Graph%2DReconstruction Problem.

Finding Representative Association Rules from Large Rule Collections.

Highlighting Diverse Concepts in Documents.
We show the underpinnings of a method for summarizing documents: it ingests a document and automatically highlights a small set of sentences that are expected to cover the different aspects of the document. The sentences are picked using simple coverage and orthogonality criteria. We describe a novel combinatorial formulation that captures exactly the document-summarization problem, and we develop simple and efficient algorithms for solving it. We compare our algorithms with many popular document-summarization techniques via a broad set of experiments on real data. The results demonstrate that our algorithms work well in practice and give high-quality summaries. 1
Intrusion Detection Technology.

Approximating the Minimum Chain Completion problem.
A bipartite graph G = (U, V, E) is a chain graph [9] if there is a bijection π: {1,..., |U|}  → U such that Γ (π (1))  ⊇ Γ (π (2))  ⊇... ⊇ Γ (π (|U|)), where Γ is a function that maps a node to its neighbors. We give approximation algorithms for two variants of the Minimum Chain Completion problem, where we are given a bipartite graph G(U, V, E), and the goal is find the minimum set of edges F that need to be added to G such that the bipartite graph G ′  = (U, V, E ′ ) (E ′  = E ∪ F) is a chain graph. 1
Constructing comprehensive summaries of large event sequences.
sequences
Constructing comprehensive summaries of large event sequences.
sequences
Interpretable nonnegative matrix decompositions.

Constructing comprehensive summaries of large event sequences.
sequences
Towards identity anonymization on graphs.
The proliferation of network data in various application domains has raised privacy concerns for the individuals involved. Recent studies show that simply removing the identities of the nodes before publishing the graph/social network data does not guarantee privacy. The structure of the graph itself, and in its basic form the degree of the nodes, can be revealing the identities of individuals. To address this issue, we study a specific graph-anonymization problem. We call a graph k-degree anonymous if for every node v, there exist at least k−1 other nodes in the graph with the same degree as v. This definition of anonymity prevents the re-identification of individuals by adversaries with a priori knowledge of the degree of certain nodes. We formally define the graph-anonymization problem that, given a graph G, asks for the k-degree anonymous graph that stems from G with the minimum number of graph-modification operations. We devise simple and efficient algorithms for solving this problem. Our algorithms are based on principles related to the realizability of degree sequences. We apply our methods to a large spectrum of synthetic and real datasets and demonstrate their efficiency and practical utility.
Determining significance of pairwise co%2Doccurrences of events in bursty sequences.

Finding links and initiators a graph reconstruction problem

Anonymizing Graphs
The proliferation of network data in various application domains has raised privacy concerns for the individuals involved. Recent studies show that simply removing the identities of the nodes before publishing the graph/social network data does not guarantee privacy. The structure of the graph itself, and in its basic form the degree of the nodes, can be revealing the identities of individuals. To address this issue, we study a specific graph-anonymization problem. We call a graph k-degree anonymous if for every node v, there exist at least k−1 other nodes in the graph with the same degree as v. This definition of anonymity prevents the re-identification of individuals by adversaries with a priori knowledge of the degree of certain nodes. We formally define the graph-anonymization problem that, given a graph G, asks for the k-degree anonymous graph that stems from G with the minimum number of graph-modification operations. We devise simple and efficient algorithms for solving this problem. Our algorithms are based on principles related to the realizability of degree sequences. We apply our methods to a large spectrum of synthetic and real datasets and demonstrate their efficiency and practical utility.
ManyAspects a system for highlighting diverse concepts in documents.

Detecting anomalous access patterns in relational databases.
Abstract A considerable effort has been recently devoted
Detecting anomalous access patterns in relational databases.
Abstract A considerable effort has been recently devoted
Nestedness and segmented nestedness.
Consider each row of a 0-1 dataset as the subset of the columns for which the row has an 1. Then a dataset is nested, if for all pairs of rows one row is either a superset or subset of the other. The concept of nestedness has its origins in ecology, where approximate versions of it has been used to model the species distribution in different locations. We argue that nestedness and its extensions are interesting properties of datasets, and that they can be applied also to domains other than ecology. We first define natural measures of nestedness and study their properties. We then define the concept of k-nestedness: a dataset is (almost) k-nested if the set of columns can be partitioned to k parts so that each part is (almost) nested. We consider the algorithmic problems of computing how far a dataset is from being k-nested, and for finding a good partition of the columns into k parts. The algorithms are based on spectral partitioning, and scale to moderately large datasets. We apply the methods to real data from ecology and from other applications, and demonstrate the usefulness of the concept.
Segmentations with Rearrangements.
Abstract. Computational genomics involves comparing sequences based on &amp;quot;similarity &amp;quot; for detecting evolutionary and functional relation-ships. Until very recently, available portions of the human genome sequence (and that of other species) were fairly short and sparse. Mostsequencing effort was focused on genes and other short units; similarity between such sequences was measured based on character level differ-ences. However with the advent of whole genome sequencing technology there is emerging consensus that the measure of similarity between long genome sequences must capture the rearrangements of large segmentsfound in abundance in the human genome. In this paper, we abstract the general problem of computing sequence similarity in the presence of segment rearrangements. This problem isclosely related to computing the smallest grammar for a string or the block edit distance between two strings. Our problem, like these otherproblems, is NP hard. Our main result here is a simple O(1) factor approximation algorithm for this problem. In contrast, best known approxi-mations for the related problems are factor \Omega (log n) off from the optimal. Our algorithm works in linear time, and in one pass. In proving our re-sult, we relate sequence similarity measures based on different segment rearrangements, to each other, tight up to constant factors. 1 Introduction Similarity comparison between biomolecular sequences play an important rolein computational genomics due to the premise that sequence similarity usually
Comparing segmentations by applying randomization techniques.

On Honesty in Sovereign Information Sharing.
Abstract. We study the following problem in a sovereign informationsharing setting: How to ensure that the individual participants, driven solely by self-interest, will behave honestly, even though they can benefit from cheating. This benefit comes from learning more than necessary private information of others or from preventing others from learning the necessary information. We take a game-theoretic approach and design a game (strategies and payoffs) that models this kind of interactions. We show that if nobody is punished for cheating, rational participants will not behave honestly. Observing this, our game includes an auditing device that periodically checks the actions of the participants and penalizes inappropriate behavior. In this game we give conditions under which there exists a unique equilibrium (stable rational behavior) in which every participant provides truthful information. The auditing device preserves the privacy of the data of the individual participants. We also quantify the relationship between the frequency of auditing and the amount of punishment in terms of gains and losses from cheating. 1
Aggregating time partitions.
Partitions of sequential data exist either per se or as a result of sequence segmentation algorithms. It is often the case that the same timeline is partitioned in many different ways. For example, different segmentation algorithms produce different partitions of the same underlying data points. In such cases, we are interested in producing an aggregate partition, i.e., a segmentation that agrees as much as possible with the input segmentations. Each partition is defined as a set of continuous non-overlapping segments of the timeline. We show that this problem can be solved optimally in polynomial time using dynamic programming. We also propose faster greedy heuristics that work well in practice. We experiment with our algorithms and we demonstrate their utility in clustering the behavior of mobile-phone users and combining the results of different segmentation algorithms on genomic sequences.
Efficient Algorithms for Sequence Segmentation.

Segmentation and dimensionality reduction.
Sequence segmentation and dimensionality reduction have been used as methods for studying high-dimensional sequences — they both reduce the complexity of the representation of the original data. In this paper we study the interplay of these two techniques. We formulate the problem of segmenting a sequence while modeling it with a basis of small size, thus essentially reducing the dimension of the input sequence. We give three different algorithms for this problem: all combine existing methods for sequence segmentation and dimensionality reduction. For two of the proposed algorithms we prove guarantees for the quality of the solutions obtained. We describe experimental results on synthetic and real datasets, including data on exchange rates and genomic sequences. Our experiments show that the algorithms indeed discover underlying structure in the data, including both segmental structure and interdependencies between the dimensions. Keywords: segmentation, multidimensional data, PCA, time series 1
Context%2Dsensitive ranking.
Abstract—The original PageRank algorithm for improving the ranking of search-query results computes a single vector, using the link structure of the Web, to capture the relative “importance ” of Web pages, independent of any particular search query. To yield more accurate search results, we propose computing a set of PageRank vectors, biased using a set of representative topics, to capture more accurately the notion of importance with respect to a particular topic. For ordinary keyword search queries, we compute the topicsensitive PageRank scores for pages satisfying the query using the topic of the query keywords. For searches done in context (e.g., when the search query is performed by highlighting words in a Web page), we compute the topic-sensitive PageRank scores using the topic of the context in which the query appeared. By using linear combinations of these (precomputed) biased PageRank vectors to generate context-specific importance scores for pages at query time, we show that we can generate more accurate rankings than with a single, generic PageRank vector. We describe techniques for efficiently implementing a large-scale search system based on the topic-sensitive PageRank scheme. Index Terms—Web search, web graph, link analysis, PageRank, search in context, personalized search, ranking algorithm.
Intrusion Detection in RBAC%2Dadministered Databases.
A considerable effort has been recently devoted to the development of Database Management Systems (DBMS) which guarantee high assurance security and privacy. An important component of any strong security solution is represented by intrusion detection (ID) systems, able to detect anomalous behavior by applications and users. To date, however, there have been very few ID mechanisms specifically tailored to database systems. In this paper, we propose such a mechanism. The approach we propose to ID is based on mining database traces stored in log files. The result of the mining process is used to form user profiles that can model normal behavior and identify intruders. An additional feature of our approach is that we couple our mechanism with Role Based Access Control (RBAC). Under a RBAC system permissions are associated with roles, usually grouping several users, rather than with single users. Our ID system is able to determine role intruders, that is, individuals that while holding a specific role, have a behavior different from the normal behavior of the role. An important advantage of providing an ID mechanism specifically tailored to databases is that it can also be used to protect against insider threats. Furthermore, the use of roles makes our approach usable even for databases with large user population. Our preliminary experimental evaluation on both real and synthetic database traces show that our methods work well in practical situations. 1.
Securing DBMS Characterizing and Detecting Query Floods.

Relational link%2Dbased ranking.
Link analysis methods show that the interconnections  between web pages have lots of valuable  information. The link analysis methods  are, however, inherently oriented towards analyzing  binary relations.
A simulated annealing approach for multimedia data placement.
Multimedy applications arecharacterized bytheir strong timing requirementsand constraintsand thusmultimedy dul storage is a critical issue in the overall system&#039;s performanceand functionality. This paperdpery)%% multimedfi dul representationmodre that e#ectivelyguid dec placementtoward the improvement of the Qualityof Presentation for the considxyw multimedw applications. The performance of both constructive   iterative improvement placement algorithms isevaluated and dduated Emphasis is given on placement schemes which arebased on the simulatedannealing optimization algorithm. A placement policy,based on a self-improving version of thesimulated annealing (SISA) algorithm isapplied and evaluated Performance of the placement policies is experimentallyevaluated on asimulated tertiarystorage subsystem. As proven bythe experimentation, the proposed approach shows considI5:yw gain in terms of seekand service times. The improvements of theproposed SISA approach are in the range of 40% whencompared torand5 placementand at the range of 15--35% whencompared to the typicalsimulated annealing algorithm,dgorithm a lot on the initial configurationand theneighborhood search.
Knowledge Representation%2C Ontologies%2C and the Semantic Web.
A unified representation for web data and web resources, is  absolutely necessary in nowdays large scale Internet data management  systems. This representation will allow for the machines to meaningfully  process the available information and provide semantically correct answers  to imposed queries. Ontologies are expected to play an important  role towards this direction of web technology which defines the so called,  Semantic Web. The goal of this paper is to provide an overview of the  Knowledge Representation (KR) techniques and languages that can be  used as standards in the Semantic Web .
Hierarchical data placement for navigational multimedia applications.
Navigat1/ has added intx&#039;&amp;M1q it in nowadaysmult imedia applicatpli whichsupport e#ectxx accessingt oobject s of various format and presen tesen requir ement1 Stnt1 issues needt be reconsidered for tr new tw1 ofnavigatq)/` mult(&amp;/x` applic in order t improvesyst m&#039;s performance. This paper addresses t1 problem ofmultM&amp; dia dat st))D t))D improving da access ibilit and request servicing undernavigat ional applicatplic Anavigat)x&#039; l graph-based model (forto mult imedia da t representes1M ) is proposedt guideti dat placement under a hierarchicalstl1fi/ tl1fi/` . The multul - iadat dependencies, access frequencies andt)M&#039;D const aint are usedt charact&amp;1q) tr graph nodes which correspondt mult(` dia obj ect allocato at t to iary sty1 ge level. Based oncertfifi defined popularit critri a,dat areelevat ed and placed on secondary leveltvel1fi improvingbot tt request servicing and dat accessibilit y. The proposedmult imediadat elevat ion is aprefet1 ing approach sinceit is performed &#034;apriori&#034;(not on demand) based on previously extusly1 user accesspats rns. Appropriat dat placement policies are also employedat t secondary level, and a simulat(D model has been developed based on current commercialtommer y and secondaryston ge devices. This model is usedt evaluat et/ proposed popularit based da televat&#039;1 approach as employed under a hierarchical stcal1 subsyst em. Experimenti ion is performed underartr1)`M dat workloads andit is showntow to proposed hierarchical da t placement approach considerably improves dat accessing and request servicing in navigati  nal mult/) dia applic atlic1 Theit1)&#039;DM( improvement placement is provent out erform earlier relati mult imediadat placement policieswit respect t commonly used performancemet ics.
A Framework for Reasoning on Objects with Geometric Constraints.

An Algorithm for Building User%2DRole Profiles in a Trust Environment.
1 Abstract. A good direction towards building secure systems that operate efficiently in large-scale environments (like the World Wide Web) is the deployment of Role Based Access Control Methods (RBAC). RBAC architectures do not deal with each user separately, but with discrete roles that users can acquire in the system. The goal of this paper is to present a classification algorithm that during its training phase, classifies roles of the users in clusters. The behavior of each user that enters the system holding a specific role is traced via audit trails and any misbehavior is detected and reported (classification phase). This algorithm will be incorporated in the Role Server architecture, currently under development, enhancing its ability to dynamically adjust the amount of trust of each user and update the corresponding role assignments. 1
A Class%2DBased Logic Language for Ontologies.

A Distributed Database Server for Continuous Media.

Querying XML with Constraints.

Multimedia Data Storage and Representation Issues on Tertiary Storage Subssystems An Overview.

